﻿// 102 最短路.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <memory.h>
using namespace std;

/*
http://oj.daimayuan.top/course/5/problem/134

给定 n个点 m条边的有向图，每条边有个边权，代表经过这条边需要花费的时间，
我们只能从编号小的点走到编号大的点，问从 1号点走到 n号点最少需要花费多少时间？

输入格式
第一行两个整数 n,m。

接下来 m行，每行三个整数 u,v,w，表示存在一条从 u到 v的边权为 w的有向边。

保证存在一条 1到 n的路径。

输出格式
输出一个数，表示答案。

样例输入
8 10
1 2 1
1 3 2
2 4 3
2 5 4
3 5 2
3 6 4
4 7 2
5 7 1
6 7 3
7 8 2
样例输出
7
数据规模
对于所有数据，保证 1≤n≤103,1≤m≤103,1≤u<v≤n,1≤w≤103。
*/

const int N = 1010;
int dp[N];
int n, m;

int gra[N][N];


int main()
{
	cin >> n >> m;
	memset(dp, 0x3f, sizeof dp);
	dp[1] = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)gra[i][j] = 0;
			else gra[i][j] = 0x3f3f3f3f;
		}
	}

	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		gra[a][b] = min(gra[a][b], c);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			dp[j] = min(dp[j], dp[i] + gra[i][j]);
		}
	}

	cout << dp[n] << endl;

	return 0;
}

 